//输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。 
//
// 
//
// 示例 1： 
//
// 输入：arr = [3,2,1], k = 2
//输出：[1,2] 或者 [2,1]
// 
//
// 示例 2： 
//
// 输入：arr = [0,1,2,1], k = 1
//输出：[0] 
//
// 
//
// 限制： 
//
// 
// 0 <= k <= arr.length <= 10000 
// 0 <= arr[i] <= 10000 
// 
//
// Related Topics 数组 分治 快速选择 排序 堆（优先队列） 👍 498 👎 0


//leetcode submit region begin(Prohibit modification and deletion)

/**
 * 利用快速排序划分数组
 * 首先判断 k 和 数组长度的关系，k >= arr.length 直接返回
 * 然后整个数组进行快速排序
 * 以数字第一个元素作为基准
 * 进行循环交换，循环条件为i < j
 *      从数组后边开始，找到第一个小于基准数的元素
 *      从第一个元素开始，找到第一个大于基准数的元素
 *      交换这两个元素，然后将基准数交换到正确位置
 * 判断 i 和 k 的关系
 *      如果相等，直接返回 i 前边的所有元素，即为最小的k个数
 *      否则，根据 i 的大小，继续划分对应部分，使 i==k
 */
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k >= arr.length) return arr;
        return quickSort(arr, k, 0, arr.length - 1);
    }
    //快速排序
    private int[] quickSort(int[] arr, int k, int l, int r) {
        int i = l, j = r;
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr, i, j);
        }
        swap(arr, i, l);
        //判断i索引，等于k就返回，否则继续划分
        if (i > k) return quickSort(arr, k, l, i - 1);
        if (i < k) return quickSort(arr, k, i + 1, r);
        return Arrays.copyOf(arr, k);
    }
    //交换
    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
